package SubjectTree.Five;

import Utility.TreeNode;

public class InsertIntoBST {

/**
 * 难度：中等
 * 
 * 701. 二叉搜索树中的插入操作
 * 	给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树
 * 	的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
 * 	
 * 注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
 * 	
 * 示例 1：
 * 	输入：root = [4,2,7,1,3], val = 5
 * 	输出：[4,2,7,1,3,5]
 * 	解释：另一个满足题目要求可以通过的树是：
 * 	
 * 示例 2：
 * 	输入：root = [40,20,60,10,30,50,70], val = 25
 * 	输出：[40,20,60,10,30,50,70,null,null,25]
 * 	
 * 示例 3：
 * 	输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
 * 	输出：[4,2,7,1,3,5]
 * 	
 * 提示：
 * 	给定的树上的节点数介于 0 和 10^4 之间
 * 	每个节点都有一个唯一整数值，取值范围从 0 到 10^8
 * 	-10^8 <= val <= 10^8
 * 	新值和原始二叉搜索树中的任意节点值都不同
 *
 * */
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		InsertIntoBST iibst = new InsertIntoBST();
		System.out.println(iibst.insertIntoBST_1(TreeNode.MkTree("[4,2,7,1,3]"), 5));
	}
	//自己写(迭代)
	public TreeNode insertIntoBST(TreeNode root, int val) {
		TreeNode node = new TreeNode(val);
        if(root==null) {
        	return node;
        }
        TreeNode parent = root;
        TreeNode cur = root;
        while(cur!=null) {
        	parent = cur;
        	if(cur.val > val)cur = cur.left;
        	else cur = cur.right;
        }
        if(val<parent.val)parent.left = node;
        else parent.right = node;
		return root;
    }
	//自己写(递归)
	public TreeNode insertIntoBST_1(TreeNode root, int val) {
		if(root == null ) {
			TreeNode node = new TreeNode(val);
			return node;
		}
		if(root.val>val)
			root.left = insertIntoBST_1(root.left, val);
		else if(root.val<val)
			root.right = insertIntoBST_1(root.right, val); 
		
		return root;
	}
	//方法一：模拟
	public TreeNode insertIntoBST1(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        TreeNode pos = root;
        while (pos != null) {
            if (val < pos.val) {
                if (pos.left == null) {
                    pos.left = new TreeNode(val);
                    break;
                } else {
                    pos = pos.left;
                }
            } else {
                if (pos.right == null) {
                    pos.right = new TreeNode(val);
                    break;
                } else {
                    pos = pos.right;
                }
            }
        }
        return root;
    }
}
